package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
*
二叉搜索树条件:

	左右子树节点，左小右大
	每一个subtree都是一个bst
	![](http://cdn.bsummer.cn/20240331211620.png)

	节点的左子树只包含小于当前节点的数。
	节点的右子树只包含大于当前节点的数。
	所有左子树和右子树自身必须也是二叉搜索树
	https://www.youtube.com/watch?v=DYNiCaKHneY&t=311s
	https://www.youtube.com/watch?v=R9YqUvSlqWY

本题容易犯的错是只考虑root和Left、Right的大小，这样的情况下可能出现root、Left、Right大小关系符合，但不满足整体BST要求，比如下图
![](http://cdn.bsummer.cn/20240331210423.png)
*/
func isValidBST(root *TreeNode) bool {
	return helper(root, -1<<31, 1<<31-1)
}

func helper(root *TreeNode, min int, max int) bool {
	if root == nil {
		return true
	}

	if root.Val < min || root.Val > max {
		return false
	}

	return (root.Val > min && root.Val < max) && helper(root.Left, min, root.Val-1) && helper(root.Right, root.Val+1, max)
}

func main() {
	r := TreeNode{Val: 1, Left: nil, Right: nil}
	l := TreeNode{Val: 0, Left: nil, Right: nil}
	r.Left = &l
	fmt.Println(isValidBST(&r))
}
